import java.util.List;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: SEKI TOMOKI
 * Date: 2023-10-07
 * Time: 16:26
 */

class PosIllegality extends RuntimeException {
    public PosIllegality(String mag) {
        super(mag);
    }
}

public class MyLinkedList implements IList{

    //节点内部类
    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }

    //定义头节点
    public ListNode head;
    //定义尾节点
    public ListNode last;
    //头插法
    @Override
    public void addFirst(int data) {
        //1.实例化一个节点且该节点的val域为data
        ListNode node = new ListNode(data);
        //2.考虑head和last为null 和 head和last不为null两种情况
        if(head == null) {
            head = node;
            last = node;
        }else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

    @Override
    public void addLast(int data) {
        //1.实例化一个节点且该节点的val域为data
        ListNode node = new ListNode(data);
        //2.考虑head和last为null 和 head和last不为null两种情况
        if(head == null) {
            head = node;
            last = node;
        }else {
            last.next = node;
            node.prev = last;
            last = node;
        }
    }

    @Override
    public void addIndex(int index, int data) throws PosIllegality{
        if(index < 0 || index > size()) {
            //抛出下标不合法异常
            System.out.println("下标不合法。");
            throw new PosIllegality("插入元素下标异常: " + index);
        }
        //3.插入
        if(index == 0) {
            addFirst(data);
        }else if(index == size()) {
            addLast(data);
        }else {
            //实例化一个节点且该节点的val域为data
            ListNode node = new ListNode(data);
            ListNode cur = search(index);//找到index位置的节点
//            ListNode curNext = cur.next;//存现在的下一个节点位置
//            cur.next = node;
//            node.next = curNext;
//            curNext.prev = node;
//            node.prev = cur;
            //修改每个节点的next
            node.next = cur;
            cur.prev.next = node;
            //修改每个节点的prev
            node.prev = cur.prev;
            cur.prev= node;
        }
    }

    private ListNode search(int index) {
        //找到index位置的节点
        ListNode cur = head;
        while(index > 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
    @Override
    public boolean contains(int key) {
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    @Override
    public void remove(int key) {
        if(head == null) {
            return ;
        }
        ListNode cur = searchKey(key);
        if(cur == head) {
            head = head.next;

            if(head != null) {//要考虑只有一个节点且要删除这个节点的情况
                head.prev = null;
            }else {
                last = null;
            }

        }else if(cur == last) {
            last = last.prev;
            last.next = null;
        }else {
            cur.prev.next = cur.next;
            cur.next.prev = cur.prev;
        }

    }
    private ListNode searchKey(int key) {
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //删除所有值为key的节点
    @Override
    public void removeAllKey(int key) {
        ListNode cur = head;
        while(cur != null) {
            if(cur.val == key) {
                if(cur == head) {
                    head = head.next;

                    if(head != null) {//要考虑只有一个节点且要删除这个节点的情况
                        head.prev = null;
                    }else {
                        last = null;
                    }

                }else if(cur == last) {
                    last = last.prev;
                    last.next = null;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
            cur = cur.next;
        }
    }

    @Override
    public int size() {
        ListNode cur = this.head;
        int count = 0;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    @Override
    public void display() {
        ListNode cur = this.head;
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    @Override
    public void clear() {
        ListNode cur = head;
        while(cur != null) {
            //cur.val = null;
            cur.prev = null;
            ListNode curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        head = null;
        last = null;
    }
}
